package leetcode_zh

import (
	"strconv"
	"strings"
)

/**
 * @Description: 面试题 01.01. 判定字符是否唯一 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/13 21:14
 **/
func isUnique(astr string) bool {
	var seen = make([]bool, 26)

	for i := 0; i < len(astr); i++ {
		if seen[astr[i]-'a'] == true {
			return false
		}
		seen[astr[i]-'a'] = true
	}
	return true
}

/**
 * @Description: 面试题 01.02. 判定是否互为字符重排 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/14 7:59
 **/
func CheckPermutation(s1 string, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	var cnt = make([]int, 26)
	for i := 0; i < len(s1); i++ {
		cnt[s1[i]-'a']++
	}
	for i := 0; i < len(s2); i++ {
		cnt[s2[i]-'a']--
	}
	for i := 0; i < 26; i++ {
		if cnt[i] != 0 {
			return false
		}
	}
	return true
}

/**
 * @Description: 面试题 01.03. URL化 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/14 8:05
 **/
func replaceSpaces(S string, length int) string {
	var res []byte
	for i := 0; i < length; i++ {
		if S[i] == ' ' {
			res = append(res, '%', '2', '0')
		} else {
			res = append(res, S[i])
		}
	}
	return string(res)
}

/**
 * @Description: 面试题 01.06. 字符串压缩 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/14 8:12
 **/
func compressString(S string) string {
	if len(S) < 2 {
		return S
	}
	var com strings.Builder
	var left int
	var right = 1
	for right < len(S) {
		if S[right] != S[left] {
			com.WriteByte(S[left])
			cntStr := strconv.Itoa(right - left)
			com.WriteString(cntStr)
			left = right
			if com.Len() >= len(S) {
				return S
			}
		}
		right++
	}
	if left == len(S)-1 {
		com.WriteByte(S[left])
		com.WriteString("1")
	} else {
		com.WriteByte(S[left])
		cntStr := strconv.Itoa(right - left)
		com.WriteString(cntStr)
	}
	if com.Len() >= len(S) {
		return S
	}
	return com.String()
}

/**
 * @Description: 面试题 01.09. 字符串轮转 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/14 8:35
 **/
func isFlipedString(s1 string, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	s3 := s2 + s2
	return strings.Contains(s3, s1)
}

/**
 * @Description: 面试题 02.01. 移除重复节点 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/14 8:47
 **/
func removeDuplicateNodes(head *ListNode) *ListNode {
	var seen = make(map[int]bool)
	var dumpyHead = &ListNode{}

	var pre = dumpyHead
	var cur = head
	for cur != nil {
		if _, ok := seen[cur.Val]; ok {
			pre.Next = cur.Next
			cur = cur.Next
		} else {
			seen[cur.Val] = true
			pre.Next = cur
			pre = cur
			cur = cur.Next
		}
	}

	return dumpyHead.Next
}

/**
 * @Description: 面试题 02.06. 回文链表 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/14 8:59
 **/
func isPalindrome06(head *ListNode) bool {
	frontPointer := head
	var recursivelyCheck func(*ListNode) bool
	recursivelyCheck = func(curNode *ListNode) bool {
		if curNode != nil {
			if !recursivelyCheck(curNode.Next) {
				return false
			}
			if curNode.Val != frontPointer.Val {
				return false
			}
			frontPointer = frontPointer.Next
		}
		return true
	}
	return recursivelyCheck(head)
}

/**
 * @Description: 面试题 02.07. 链表相交 简单
 * @Keyword: 双指针，2020年面试B站时遇到过这道题
 * @Author: kami
 * @Date: 2022/8/15 9:06
 **/
func getIntersectionNode07(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	var curA = headA
	var curB = headB
	var turnA = false
	var turnB = false

	for curA != curB {
		if curA.Next != nil {
			curA = curA.Next
		} else {
			if turnA {
				return nil
			} else {
				curA = headB
				turnA = true
			}
		}

		if curB.Next != nil {
			curB = curB.Next
		} else {
			if turnB {
				return nil
			} else {
				curB = headA
				turnB = true
			}
		}
	}
	return curA
}

/**
 * @Description: 面试题 03.02. 栈的最小值 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/8/15 10:23
 **/
type MinStack02 struct {
	stack []*ele
}
type ele struct {
	val    int
	curMin int
}

/** initialize your data structure here. */
func Constructor02() MinStack02 {
	return MinStack02{stack: make([]*ele, 0)}
}

func (this *MinStack02) Push02(x int) {
	new := &ele{
		val: x,
	}
	if len(this.stack) == 0 {
		new.curMin = x

	} else {
		curMin := this.stack[len(this.stack)-1].curMin
		if x < curMin {
			curMin = x
		}
		new.curMin = curMin
	}
	this.stack = append(this.stack, new)
}

func (this *MinStack02) Pop02() {
	this.stack = this.stack[0 : len(this.stack)-1]
}

func (this *MinStack02) Top02() int {
	return this.stack[len(this.stack)-1].val
}

func (this *MinStack02) GetMin02() int {
	return this.stack[len(this.stack)-1].curMin

}

/**
 * @Description: 面试题 03.04. 化栈为队 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/8/15 13:40
 **/
type MyQueue struct {
	head *QueueNode
	size int
}
type QueueNode struct {
	val  int
	pre  *QueueNode
	next *QueueNode
}

/** Initialize your data structure here. */
func Constructor04() MyQueue {
	return MyQueue{}
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
	node := &QueueNode{
		val: x,
	}
	if this.head == nil {
		node.pre = node
		node.next = node
		this.head = node
		this.size++
		return
	}
	tail := this.head.pre
	tail.next = node
	node.pre = tail
	this.head.pre = node
	this.size++
	return
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
	if this.size == 1 {
		val := this.head.val
		this.head = nil
		this.size--
		return val
	}
	tail := this.head.pre
	val := this.head.val
	next := this.head.next
	this.head.next = nil
	this.head.pre = nil
	next.pre = tail
	this.head = next
	this.size--
	return val
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
	return this.head.val
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
	return this.size == 0
}

/**
 * @Description: 面试题 03.01. 三合一 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/15 14:00
 **/
type TripleInOne struct {
	S   []int
	Len []int
	Cap int
}

func Constructor01(size int) TripleInOne {
	return TripleInOne{
		make([]int, size*3),
		make([]int, 3),
		size,
	}
}
func (this *TripleInOne) Push(num int, value int) {
	if this.Len[num] == this.Cap {
		return
	}
	this.S[num*this.Cap+this.Len[num]] = value
	this.Len[num]++
}
func (this *TripleInOne) Pop(num int) int {
	if this.Len[num] == 0 {
		return -1
	}
	x := this.S[num*this.Cap+this.Len[num]-1]
	this.Len[num]--
	return x
}
func (this *TripleInOne) Peek(num int) int {
	if this.Len[num] == 0 {
		return -1
	}
	return this.S[num*this.Cap+this.Len[num]-1]
}
func (this *TripleInOne) IsEmpty(num int) bool {
	return this.Len[num] == 0
}

/**
 * @Description: 面试题 04.02. 最小高度树 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/15 16:42
 **/
func sortedArrayToBST(nums []int) *TreeNode {

	var build func(nums []int, left, right int) *TreeNode

	build = func(nums []int, left, right int) *TreeNode {
		if left == right {
			return nil
		}

		var mid = (left + right) / 2
		cur := &TreeNode{
			Val: nums[mid],
		}
		cur.Left = build(nums, left, mid)
		cur.Right = build(nums, mid+1, right)
		return cur
	}
	return build(nums, 0, len(nums)-1)

}

/**
 * @Description: 面试题 04.04. 检查平衡性 简单
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/8/16 10:27
 **/
func isBalanced04(root *TreeNode) bool {
	var isbanance = true
	var depth func(node *TreeNode) int
	depth = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		var left = depth(node.Left)
		var right = depth(node.Right)
		var diff = abs(left - right)
		if diff > 1 {
			isbanance = false
			return 0
		}
		if left > right {
			return left + 1
		}
		return right + 1
	}

	depth(root)

	return isbanance
}

/**
 * @Description: 面试题 05.01. 插入 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/16 11:28
 **/
func insertBits(N int, M int, i int, j int) int {
	nj := N >> (uint(j) + 1) << (uint(j) + 1)
	ni := (N >> uint(i) << uint(i)) ^ N
	nz := ni | nj
	return nz | M<<uint(i)
}

/**
 * @Description: 面试题 05.06. 整数转换 简单
 * @Keyword: 异或，右移位
 * @Author: kami
 * @Date: 2022/8/19 9:36
 **/
func convertInteger(A int, B int) int {
	var cnt int
	var and = A ^ B
	for i := 0; i < 32; i++ {
		cnt += and & 1
		and >>= 1
	}
	return cnt
}

/**
 * @Description: 面试题 05.07. 配对交换 简单
 * @Keyword: 移位
 * @Author: kami
 * @Date: 2022/8/19 9:50
 **/
func exchangeBits(num int) int {
	//0xaaaaaaaa 10101010101010101010101010101010 (偶数位为1，奇数位为0）
	even := (num & 0b10101010_10101010_10101010_10101010) >> 1 // 获取当前数字的偶数位，然后向右移动一位
	//0x55555555  1010101010101010101010101010101 (偶数位为0，奇数位为1）
	odd := (num & 0b01010101_01010101_01010101_01010101) << 1 // 获取当前位数的奇数 然后向左移动一位
	return even | odd
}

/**
 * @Description: 面试题 01.04. 回文排列 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/20 9:05
 **/
func canPermutePalindrome(s string) bool {
	var seen = make([]bool, 128)

	for i := 0; i < len(s); i++ {
		seen[s[i]] = !seen[s[i]]
	}
	var single bool
	for i := 0; i < 128; i++ {
		if seen[i] == true {
			if single {
				return false
			}
			single = true
		}
	}
	return true
}

/**
 * @Description: 面试题 02.03. 删除中间节点
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/20 9:17
 **/
func deleteNode03(node *ListNode) {
	node.Val = node.Next.Val
	node.Next = node.Next.Next
}

/**
 * @Description:面试题 08.01. 三步问题 简单
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/8/20 9:22
 **/
func waysToStep(n int) int {
	var first = 1
	var second = 2
	var third = 4

	if n <= 2 {
		return n
	}
	if n == 3 {
		return third
	}

	for i := 4; i <= n; i++ {
		var cur = (first + second + third) % 1000000007
		first = second
		second = third
		third = cur
	}
	return third
}

/**
 * @Description: 面试题 08.10. 颜色填充 简单
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/8/20 9:29
 **/
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	var old = image[sr][sc]
	if old == newColor {
		return image
	}
	var dfs func(img [][]int, row, col, old, new int)
	dfs = func(img [][]int, row, col, old, new int) {
		if row < 0 || row == len(img) || col < 0 || col == len(img[0]) || img[row][col] != old {
			return
		}
		img[row][col] = new
		// 上
		dfs(img, row-1, col, old, new)
		// 下
		dfs(img, row+1, col, old, new)
		// 左
		dfs(img, row, col-1, old, new)
		// 右
		dfs(img, row, col+1, old, new)
	}
	dfs(image, sr, sc, old, newColor)
	return image
}

/**
 * @Description: 面试题 03.06. 动物收容所 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/8/26 8:38
 **/
type AnimalShelf struct {
	// 编号 0猫 1狗
	cat []int
	dog []int
}

func Constructor06() AnimalShelf {
	return AnimalShelf{}
}

func (this *AnimalShelf) Enqueue(animal []int) {
	if animal[1] == 0 {
		this.cat = append(this.cat, animal[0])
	} else {
		this.dog = append(this.dog, animal[0])
	}
}

func (this *AnimalShelf) DequeueAny() []int {
	if len(this.cat) == 0 && len(this.dog) == 0 {
		return []int{-1, -1}
	}
	if len(this.cat) > 0 && len(this.dog) > 0 {
		if this.cat[0] < this.dog[0] {
			oldCat := this.cat[0]
			this.cat = this.cat[1:]
			return []int{oldCat, 0}
		} else {
			oldDog := this.dog[0]
			this.dog = this.dog[1:]
			return []int{oldDog, 1}
		}
	} else if len(this.cat) > 0 {
		oldCat := this.cat[0]
		this.cat = this.cat[1:]
		return []int{oldCat, 0}
	}
	oldDog := this.dog[0]
	this.dog = this.dog[1:]
	return []int{oldDog, 1}
}

func (this *AnimalShelf) DequeueDog() []int {
	if len(this.dog) == 0 {
		return []int{-1, -1}
	}
	oldDog := this.dog[0]
	this.dog = this.dog[1:]
	return []int{oldDog, 1}
}

func (this *AnimalShelf) DequeueCat() []int {
	if len(this.cat) == 0 {
		return []int{-1, -1}
	}
	oldCat := this.cat[0]
	this.cat = this.cat[1:]
	return []int{oldCat, 0}
}

/**
 * @Description: 面试题 05.03. 翻转数位 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/27 15:27
 **/
func reverseBits(num int) int {
	var prer, ans, cur int

	for i := 0; i < 32; i++ {
		if (1<<i)&num == 0 {
			if cur+prer+1 > ans {
				ans = cur + prer + 1
			}
			prer = cur
			cur = 0
		} else {
			cur++
		}
	}
	//最后一位可能不是0或者总共只有一个0
	if cur+prer+1 > ans {
		ans = cur + prer + 1
	}
	if ans > 32 {
		return 32
	}
	return ans
}

/**
 * @Description: 面试题 08.03. 魔术索引 简单
 * @Keyword: 暴力或者二分查找
 * @Author: kami
 * @Date: 2022/8/27 15:40
 **/
func findMagicIndex(nums []int) int {
	for i := 0; i < len(nums); i++ {
		if i == nums[i] {
			return i
		}
	}
	return -1
}

func findMagicIndex03(nums []int) int {
	return getAnswer(nums, 0, len(nums)-1)
}

func getAnswer(nums []int, left, right int) int {
	if left > right {
		return -1
	}
	mid := (right-left)/2 + left
	leftAnswer := getAnswer(nums, left, mid-1)
	if leftAnswer != -1 {
		return leftAnswer
	} else if nums[mid] == mid {
		return mid
	}
	return getAnswer(nums, mid+1, right)
}

/**
 * @Description: 面试题 10.05. 稀疏数组搜索 简单
 * @Keyword: 二分查找
 * @Author: kami
 * @Date: 2022/9/9 7:58
 **/
func findString(words []string, s string) int {
	var left int
	var right = len(words) - 1
	for left <= right {
		for left <= right && words[left] == "" {
			left++
		}
		for right >= left && words[right] == "" {
			right--
		}
		var mid = (left + right) / 2
		for mid <= right && words[mid] == "" {
			mid++
		}
		if words[mid] == s {
			return mid
		}
		if strings.Compare(words[mid], s) > 0 {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

/**
 * @Description: 面试题 16.07. 最大数值 简单
 * @Keyword: 补位
 * @Author: kami
 * @Date: 2022/9/25 16:37
 **/
func maximum(a int, b int) int {
	//整数右移高位补0,负数右移高位补1
	//a>b,ret>0,temp&1=0
	//a<b,ret<0,temp&1=1
	ret := int64(a - b)
	ret = int64(a) - ret&(ret>>63)
	return int(ret)
}

/**
 * @Description: 面试题 16.11. 跳水板 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/9/25 16:49
 **/
func divingBoard(shorter int, longer int, k int) []int {
	if k == 0 {
		return []int{}
	}
	if shorter == longer {
		return []int{shorter * k}
	}
	lengths := make([]int, k+1)
	for i := 0; i <= k; i++ {
		lengths[i] = shorter*(k-i) + longer*i
	}
	return lengths
}

/**
 * @Description: 面试题 16.15. 珠玑妙算 简单
 * @Keyword: 猜中，伪猜中
 * @Author: kami
 * @Date: 2022/10/29 8:59
 **/
func masterMind(solution string, guess string) []int {
	a := map[byte]int{}
	for i := range solution {
		a[solution[i]]++
	}
	c := 0
	for i := range guess {
		if a[guess[i]] > 0 {
			c++
			a[guess[i]]--
		}
	}
	d := 0
	for i := range solution {
		if solution[i] == guess[i] {
			d++
		}
	}
	return []int{d, c - d}
}
